package leetcode.datastructure.binarytree;

import common.bean.ListNode;
import common.bean.TreeNode;

import java.util.ArrayList;
import java.util.List;


public class Program637LevelAverage {

    public Program637LevelAverage() {
    }
    public List<Double> averageOfLevels(TreeNode root) {
        return BFS(root);
    }

    public List<Double> BFS(TreeNode root) {
        List<Double> res = new ArrayList<>();
        List<TreeNode> level = new ArrayList<>();
        level.add(root);
        List<TreeNode> tmp = null;
        long sum = 0;
        while (level.size() > 0) {
            tmp = new ArrayList<>();
            for (int i = 0; i < level.size(); i++) {
                TreeNode treeNode = level.get(i);
                sum += treeNode.val;
                if (treeNode.left != null) {
                    tmp.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    tmp.add(treeNode.right);
                }
            }
            Double ans = (double)sum / level.size();
            res.add(ans);
            level = tmp;
            sum = 0;
        }
        return res;
    }

    public static void main(String[] args) {
    }
}
